package com.c2b.algorithm.leetcode.base;

import java.util.*;

/**
 * <a href="https://leetcode.cn/problems/insert-delete-getrandom-o1/description/?envType=study-plan-v2&envId=top-interview-150">O(1) 时间插入、删除和获取随机元素(Insert Delete GetRandom O(1))</a>
 * <p>
 * 实现RandomizedSet 类：
 * <ul>
 *     <li>RandomizedSet() 初始化 RandomizedSet 对象</li>
 *     <li>bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。</li>
 *     <li>bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。</li>
 *     <li>int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。</li>
 *     <li></li>
 * </ul>
 * 你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。
 * </p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  输入
 *      ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
 *      [[], [1], [2], [2], [], [1], [2], []]
 *  输出
 *      [null, true, false, true, 2, true, false, 2]
 *
 *  解释
 *      RandomizedSet randomizedSet = new RandomizedSet();
 *      randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
 *      randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
 *      randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
 *      randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
 *      randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
 *      randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
 *      randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
 * </pre>
 * </p>
 * <b>提示：</b>
 * <ul>
 *     <li>-2^31 <= val <= 2^31 - 1</li>
 *     <li>最多调用 insert、remove 和 getRandom 函数 2 * 10^5 次</li>
 *     <li>在调用 getRandom 方法时，数据结构中 至少存在一个 元素。</li>
 * </ul>
 *
 * @author c2b
 * @since 2023/10/10 11:13
 */
public class LC0380InsertDeleteGetRandom_M {

    static class RandomizedSet {
        // 值 与 在数组中所在索引的map
        Map<Integer, Integer> data2IndexMap;
        List<Integer> dataList;
        Random random = new Random();

        public RandomizedSet() {
            data2IndexMap = new HashMap<>();
            dataList = new ArrayList<>();
        }

        public boolean insert(int val) {
            if (data2IndexMap.containsKey(val)) {
                return false;
            }
            dataList.add(val);
            data2IndexMap.put(val, dataList.size() - 1);
            return true;
        }

        public boolean remove(int val) {
            // 首先判断 val 是否在哈希表中，如果不存在则返回 false
            if (!data2IndexMap.containsKey(val)) {
                return false;
            }
            // 1.从哈希表中获得 val 的下标 index；
            Integer index = data2IndexMap.get(val);
            // 2.将变长数组的最后一个元素 lastIndexVal 移动到下标 index 处，在哈希表中将 lastIndexVal 的下标更新为 index；
            Integer lastIndexVal = dataList.get(dataList.size() - 1);
            dataList.set(index, lastIndexVal);
            data2IndexMap.put(lastIndexVal, index);
            // 3.在变长数组中删除最后一个元素，在哈希表中删除 val
            dataList.remove(dataList.size() - 1);
            data2IndexMap.remove(val);
            return true;
        }

        public int getRandom() {
            return dataList.get(random.nextInt(dataList.size()));
        }
    }

    public static void main(String[] args) {
        RandomizedSet obj = new RandomizedSet();
        System.out.println(obj.insert(1));
        System.out.println(obj.remove(2));
        System.out.println(obj.insert(2));
        System.out.println(obj.remove(1));
        System.out.println(obj.insert(2));
        int param_3 = obj.getRandom();
        System.out.println(param_3);
    }
}
